package com.classicInterview;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: huangzhigao
 * @Date: 2022/2/12 15:02
 */
public class AimSum {

    /**
     * 求解和为aim的不同二元组
     *
     * @param arr
     * @param aim
     * @return
     */
    public List<Object> twoSumAim(int[] arr, int aim) {

        ArrayList<Object> objects = new ArrayList<>();
        int l = 0;
        int r = arr.length - 1;
        while (l < r) {
            if (arr[l] + arr[r] > aim) {
                r--;
            } else if (arr[l] + arr[r] < aim) {
                l++;
            } else {
                if (l > 0 && arr[l - 1] != arr[l]) {
                    objects.add(new int[]{arr[l], arr[r]});
                }
            }
        }
        return objects;
    }


    /**
     * 求解和为aim的不同三元组
     *
     * @param arr
     * @param aim
     * @return
     */
    public List<Object> treeSumAim(int[] arr, int aim) {

        ArrayList<Object> objects = new ArrayList<>();
        for (int i = 0; i < arr.length - 3; i++) {
            //求出的二元组加上自己，即为答案
            if (i > 0 && arr[i - 1] != arr[i]) {
                twoSumAim(arr, aim - arr[i]);
            }
        }
        return objects;
    }

}
